//
// Created by 21577 on 2025/4/9.
//
#include<stdio.h>
#include<stdlib.h>
// 定义链表节点结构
typedef struct Node{
    int data;
    struct Node* next;
}Node;
// 初始化头节点
Node* initList(){
    return NULL;
}
// 创建新的节点
Node* createNode(int data){
    Node * newnode = (Node*) malloc(sizeof (Node));
    if(newnode == NULL){
        printf("内存分配失败！");
        exit(1);
    }
    newnode->data = data;
    newnode->next = NULL;
    return newnode;
}
// 在循环链表头部插入新的节点
Node* insertAtHead(Node* head, int data){
    Node* newnode = createNode(data);
    if(head == NULL){
        newnode->next = newnode;
    }else{
        Node* last = head;
        while(last->next != head){
            last = last->next;
        }
        newnode->next = last->next;
        last->next = newnode;
    }
    return newnode;
}
// 在循环链表的尾部插入新的节点
Node* insertAtTail(Node* head, int data){
    Node* newnode = createNode(data);
    if(head == NULL){
        newnode = newnode->next;
        return newnode;
    }else{
        Node* last = head;
        while(last->next != head){
            last = last->next;
        }
        newnode->next = last->next;
        last->next = newnode;
    }
    return head;
}
// 打印循环链表
void travalList(Node* head){
    if(head == NULL) {
        printf("链表为空！\n");
        return;
    }else{
        Node* current = head;
        do{
            printf("%d  ",current->data);
            current = current->next;
        }while(current != head);
        printf("\n");
    }
}
// 删除头节点
Node* deleteHead(Node* head){
    if(head == NULL){
        return NULL;
    }else{
        Node* last = head;
        while(last->next != head){
            last = last->next;
        }
        Node* temp = head;
        head = head->next;
        last->next = head;
        free(temp);
        return head;
    }
}
// 释放内存空间
void FreeList(Node* head){
    if(head == NULL){
        return;
    }else{
        Node* current = head;
        Node* next;
        do{
            next = current->next;
            free(current);
            current = next;
        }while(current != head);
    }
}
int main(){
    Node* head = initList();
    // 在头部插入元素
    head = insertAtHead(head,1);
    head = insertAtHead(head,2);
    head = insertAtHead(head, 3);
    travalList(head);
    // 在尾部插入元素
    head = insertAtTail(head, 3);
    head = insertAtTail(head, 4);
    head = insertAtTail(head, 5);
    travalList(head);
    // 删除头节点
    head = deleteHead(head);
    travalList(head);
    // 释放链表内存空间
    FreeList(head);
//    travalList(head);

    return 0;
}